\documentclass[a4paper,10pt]{article}
\usepackage{amssymb,amsmath,graphicx,float,hyperref}
\title{Bachelor Thesis - Intelligent Traffic Management}
\author{Burkhard von der Osten}

\begin{document}
\maketitle
%\tableofcontents%

\begin{abstract}
This paper deals with the optimization of traffic flow on road networks. Nowadays the issue of optimizing transportation in urban areas is becoming increasingly important. Due to dense population and growing economies, sea, land and air traffic are massively increasing. This increase leads to an overuse of the existing infrastructure. Thus new methods of organizing this traffic have to be developed. Approaches to improve the flow of traffic on road networks have been made in several directions. This paper will elaborate on different categories of optimization methods and their advantages and disadvantages.
\end{abstract}

\section{Introduction}
As the problem of traffic optimization becomes more urgent, numerous improvements and solutions have been suggested. Some of these are based on future infrastructure layouts that allow autonomous vehicles within the traffic \cite{dresner} or on collective hardware changes at intersections (installing means of communication) both from single and multi-agent perspectives. This paper concentrates on decentralized approaches, where single intersections are managed independently [possibly with information received by neighboring intersections] and their traffic throughput shall be increased. The suggested decentralized approaches can be categorized by their type of dynamics. The aim of this paper is to compare algorithms of different categories to determine which approach promises the most success in terms of performance omprovement and adaptability. The situation assumed is modern up-to-date infrastructure that does not need to be altered, so the improvement is supposed to come solely from intelligent software.\\

The paper is organized as follows: The [next] section will give an overview over the field and related work, the [third] section will explain the traffic simulator used and the assumptions made to create the specified environment. The [fourth] section will elaborate on the different algorithms used, whereas the [fifth] section describes the experiments setup and the results. Finally the [sixth] section will conclude the paper and also give some future outline.

\section{Related work}
The field of intelligent traffic management is very wide and thus this paper concentrates on the smaller area of decentralized systems. \\
-Wiering \cite{wiering}, Dresner \cite{dresner}, Oliveira \cite{oliveira}, Gershenson \cite{gershenson}...?\\
-reinforcement learning, Q-learning, TD-learning, MAS...?\\

To make comparison easier, categories for traffic management systems are devised. There are three categories, the first of which are static methods. These methods do not allow any adaptation to the traffic situation in real-time. Once set, only offline-adaption can take place. The second category are semi-dynamic methods, where adaption rules or models are defined beforehand and cannot be altered online. Still these methods are dynamic with regard to the reaction behaviour to traffic changes. The last category are full-dynamic methods. These methods adapt their rules and models online real-time and are thus completely independent of premade models or rules other than certain reward functions to implement their goals.

\section{Traffic simulator}
Short section introduction
\subsection{Approach}
There are two major approaches to create traffic simulations, which are the microscopic or macroscopic view. From a macroscopic perspective the continuous flow of traffic in general is observed and measured by means such as speed, flow and density by looking at the whole traffic system. Modern models for that approach include fluid dynamics and gas kinetic models. A microscopic approach in comparison predicts the state of every individual vehicle by means of speed and location. For this approach often physical models and motion equations are used. A mixture of both perspectives is called a mesoscopic model \cite{pursula}. 

For the simulations in this paper a microscopic approach has been used, since in particular intersections are investigated and therefore the interest lies in how many vehicles an intersection can process, which is why these vehicles have to be modeled individually. Additionally simulation models can be classified by functionality, for example signal, freeway or integrated. The approach used is based on a freeway model, whereas it is used more in a signal context.
\subsection{Model}
For the chosen approach there exist two popular models that are commonly used, the Intelligent Driver Model (IDM) \cite{treiber} and the Nagel-Schreckenberg cellular automaton \cite{nagelschreckenberg}. The IDM is a car-following model that uses the following ordinary differential equations to describe position

\begin{equation}
\dot{x}_\alpha = \frac{\partial x_\alpha}{\partial t} = v_\alpha
\end{equation}

and velocity

\begin{equation}
\dot{v}_\alpha = \frac{\partial v_\alpha}{\partial t} = a \left(1 - \left(\frac{v_\alpha}{v_0}\right)^\delta - \left(\frac{s_0 + v_\alpha T + \frac{v_\alpha \Delta v}{2 \sqrt{a b}}}{s_\alpha}\right)^2\right)
\end{equation}

of vehicle $\alpha$, where $s_\alpha$ is the net distance between vehicle $\alpha$ and the vehicle in front of it and $\Delta v_\alpha$ is the velocity difference of the two vehicles. $v_0, s_0, T, a, b$ and $\delta$ are constants.
These formulas guarantee a continuous traffic simulation and they only depend on constants and the vehicle being followed. In case there is no vehicle, normal acceleration takes place.

The Nagel-Schreckenberg model uses cellular automata to describe the vehicle's position and speed. A road is made of equal length cells, each of which can hold exactly one vehicle and one vehicle can only be in one cell. The vehicles speed is discretized, usually in five steps, where the number of steps is the number of cells moved forward. The vehicles move according to the following rules then: 

\begin{enumerate}
\item{Acceleration:
If the vehicle's speed is lower than the maximum speed and the distance to the next vehicle in front is more than the vehicle's speed, accelerate by one speed step.}
\item{Deceleration: If the distance to the next vehicle in front is less than the vehicle's speed, the speed is set to the distance between the two vehicles to prevent a crash. Additionally, if a traffic light ahead is red and the distance of the vehicle to the traffic light is less than the vehicle's speed, the speed is also set to the distance between the vehicle and the traffic light. This rule makes sure that a vehicle slows down in front of a red traffic light.}
\item{Slowdown: The vehicle's speed is reduced by one speed step with slowdown probability $p$. This rule implements brake delay, lack of driver attention and other factors.}
\item{Motion: All vehicles are moved by their current speed, i.e. if a vehicle has speed $v$ it is moved forward by $v$ cells.}
\end{enumerate}

This model can be simplified by using a list of vehicles instead of cells, such that unoccupied cells do not have to be modeled. Both models are devised for single-lane traffic simulation, whereas they can be extended to multi-lane purpose.\\
For the traffic simulator being used to conduct the experiments in this paper, the simplified Nagel-Schreckenberg model has been used, because it is computationally cheap and more coarse than the IDM. The discretization makes the implementation easier, yet it contains all essential elements to simulate traffic at intersections and allows full measurability while maintaining simplicity.
The model has been implemented with single-lane functionality, since [reason].
Some models introduce additional features like [Wiering's routing], which are not necessarily suitable for a realistic approach, since [reason].
\subsection{Assumptions}
The basic directive to develop a traffic simulator is to keep it simple. The environment should be discretized as far as possible to allow easier calculations and more precision. Therefore a couple of assumptions for implementation were made. These will be explained in this section.

In the traffic simulator one kind of vehicle is used, an average car, although other vehicles with different properties can be introduced easily. It has a position, velocity and maximum speed and is placed on a road by adding it to the list representing the road. The direction of a vehicle does not change [give reason here? easy to measure, no confusion, especially concerning spawn patterns] throughout the entire existence in the system. Once a vehicle reaches an end of the system, it is removed. 

New vehicles entering the system are placed onto a road entering the system accoring to a spawning probability. This spawning probability can change and thus represent a change in the traffic pattern. If the road is full, no vehicle can be spawned, there is no queue for vehicles waiting to enter the system. The road itself has a speedlimit that overrides the vehicle's maximum speed. The cells on a road are only virtual, since empty cells are not modeled. One virtual cell has a length of 7.5 $m$. The speed of a vehicle is discretized into five steps, where one step is 27.5 $km/h$ accordingly.

An intersection has four incoming and four outgoing lanes in the four principle directions (north, east, south and west) and four traffic lights for the incoming lanes, which can take either states \emph{red} or \emph{green}. If a light is red, all vehicles on the accoring road slow down and stop when approach the light or the vehicles queueing up respectively.

The occupation of a road is categorized to be empty, regular or full to enable the learning algorithms to evaluate a traffic situation. Furthermore the traffic produced is categorized by its amount into low, normal and busy traffic, where low traffic is easily handled, normal traffic uses full capacity of intersections and busy traffic exceeds the full capacity of an intersection. Traffic patterns are defined by each one of the principle directions, and traffic only flows in one direction as mentioned with the vehicles.

\section{Algorithms}
This section presents the four categories of algorithms that are used to control the intersections in the traffic simulator and explains how they work. 
\subsection{Simple Phase Switch}
This algorithm gives an equal amount of time for the traffic lights to be green for every direction. The phases switch in the order North, East, South, West, where only one light can be green at a time, meaning as soon as the phase switches the new direction will become green and the old direction will turn red. This algorithm represents a class of static methods that will not change once initiated and thus have to be carefully balanced.
\subsection{Greedy}
The greedy algorithm is a simple implementation of self-organizing traffic lights. It measures the cars waiting on every incoming lane and gives green light to the lane with the most waiting cars. Waiting is here defined as having a speed of zero. All other lights have to be red. This algorithm belongs to the class of semi-dynamic algorithms already, as it adapts to the traffic situation with a simple heuristic.
\subsection{Self-organizing Transportation}
Gershenson's self-orgarnizing transportation algorithm is a more advanced implementation of self-organizing traffic lights \cite{gershenson}. Gersheson defines six rules to be obeyed, four of which were implemented:

\begin{enumerate}
\item{If the number of vehicles waiting at the traffic light within distance $d$ exceeds threshold $n$, switch the traffic light to the respective lane.}
\item{Every traffic light has a minimum green time of $u$ rounds.}
\item{If more than 0 and less than $m$ vehicles are left to cross the light within a distance $r$, the light remains green.}
\item{If no vehicle is arriving within distance $d$ at a green light and at least one vehicle is arriving within distance $d$ at a red light, switch the light.}
\end{enumerate}
The last two rules

\begin{itemize}
\item{If a vehicle is stopped on a road beyond a green traffic light within a distance $e$, switch the light to red.}
\item{If vehicles are stopped on both directions beyond the green lights within a distance $e$, switch both lights to red. As soon as one lane is free again, restore the green light.}
\end{itemize}

 were not necessary due to the architecture of the simulator, since firstly only one traffic light can be green at a time and secondly cars cannot be stopped beyond traffic lights (they would not cross the intersection in the first place if the road beyond was full). This algorithm also belongs to the class of semi-dynamic algorithms as it adapts to the traffic situation by several heuristics and predefined rules.
\subsection{Reinforcement Learning}
This model-based reinformcement learning algorithm is an adapted implementation of [the reinforcement learning context decision (RL-CD) algorithm by Oliveira \cite{oliveira}]. [further/detailed explanation] [formulas]\\

\begin{equation}
\Delta ^T_{m,\varphi} (\kappa) = \frac{1}{N_m(s, a) + 1} \left(\tau^{s'}_\kappa - T_m(s, a \kappa)\right) \forall \kappa \in S
\end{equation}

\begin{equation}
\Delta ^R_{m, \varphi} = \frac{1}{N_m(s, a) + 1} \left( r - R_m(s, a)\right)
\end{equation}

\begin{equation}
\tau ^{s'}_\kappa = \left\{\begin{array}1, \kappa = s' \\ 0, \kappa \neq s' \end{array}\right
\end{equation}

This algorithm is part of the class of fully-dynamic algorithms, which can adapt to traffic flow and changes therein by creating new rules and online-learning from the context.
\subsection{Enhancements}
-possibly add own implementation (added information for learning and Gershenson) even if performance lower?

\section{Experiments}
-one or two sentences as section introduction?
\subsection{Setup}
All experiments have been set up with two different environments: a single intersection and a map of 9 intersections in a square. The reason for using these different scenarios is [that some methods seem to perform really well in an isolated intersection but fail to deal with dynamic traffic situations, which should be pointed out by the comparing the results of the two scenarios]. In the experiments conducted a number of measures have been used for comparison. The most important measure is the average total travel time of a vehicle in the system, which desirably should be reduced. Additionally the average waiting time of a car in the system, the number of cars entering and exiting the system and the average number of cars waiting per round are measured. Every simulation runs for [...] steps and for every method the simulation is carried out [...] times and average values of the measures are taken.\\
-compare the 4 categories of methods\\
-with and without changing of traffic situation (change of spawning probabilities over time, different at different places)\\
-try mix of methods?\\
-compare with and without including information from neighboring intersections?\\
\subsection{Results \& Interpretation}
we will see...
\section{Conclusion}
-dynamic environments more realistic, decentralized approach more reasonable\\
-learning algorithms not superior
\subsection{Future work}
-combine algorithms, develop real full-dynamic (model-free, no partial models needed)

\section{Unsorted notes, not part of the report}
-using new approach to overcome communication bottlenecks: neighboring intersection provides traffic data (decentralized approach)\\
-model simulator: for drivers: network as a graph, where every lane is a node, lane should get own datastructure to model traffic on it (drivers know their route), such that a sequence of intersections can be modeled as well (start out with one only)\\
-learning signal plan selection? how could it work without signal plans anw?\\
-model single traffic light as agent or all lights of an intersection?\\
-driver agents have behaviours\\
-probability for a type of vehicle to appear: simply select uniformly random number and determine interval\\
-reinforcementLearningTrafficLlights uses estimation of flow pattern (learning contexts) and division into partial models (RL with context decisions)\\
-keep it simple: easy scenario, discretize, few possible states (categorize with thresholds), first one type of driver, later more (parade maker, too fast, trucks, etc.)\\

-learn traffic lights OR learn cars?\\
-in crowded traffic, longer tl cycles lead to better performance (who said that? can show it is false)\\
-value function car based or traffic light based?\\
-criticise: wiering approach to keep in mind global destination not applicable (especially for long routes, i.e. use navigation system)\\
-gershenson: notion of platoons, explain and investigate (only with multiple intersections, since platoons are formed by light phases)\\
-implement above approach (Olivieira et al.) and see if i can get comparable or better results, implement gershenson as well (easy)\\
-implementation specifics nagel-schreckenberg: use arraylist of cars as a lane?\\

-make the results comparable (discretization of state space)\\
-a simple 2-lanes implementation would not change anything, only if different directions / turns are added, it is just a matter of setting up the scenario and this one is simple since there is not too much randomness (lanechanging and direction adds a lot of randomness to the traffic situation and then outcomes can be misinterpreted)\\
-limitations of 1-lane model


\bibliographystyle{plain}
\bibliography{references}
\end{document}